package com.example.demo.node;

/**
 * 单链表
 *
 * @author GXYH
 * @date 2021/08/13
 */
public class SinglyListNode {
    class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    int size;
    Node head;

    public SinglyListNode() {
        this.size = 0;
        this.head = null;
    }

    public int get(int index) {
        //下标错误或者空节点，则返回-1
        if (index < 0 || index >= size || head == null) {
            return -1;
        }
        //找出头节点
        Node temp = this.head;
        //循环找出index节点
        for (int x = 0; x < index; x++) {
            temp = temp.next;
        }
        return temp.data;
    }

    public void addAtHead(int val) {
        //创建节点
        Node node = new Node(val);
        //将此节点的下个节点指向头节点
        node.next = this.head;
        //头节点则变成了当前创建的节点
        this.head = node;
        //添加节点数量
        size++;
    }

    public void addAtTail(int val) {
        //创建新节点
        Node node = new Node(val);
        //如果节点数量为0，头节点则是当前节点
        if (size == 0) {
            this.head = node;
        } else {
            //找到头节点
            Node temp = this.head;
            //如果有下一个节点，循环找到最后一个节点
            while (temp.next != null) {
                temp = temp.next;
            }
            //将当前节点设置为最后一个节点的下一个节点
            temp.next = node;
        }
        //添加节点数
        size++;
    }

    public void addAtIndex(int index, int val) {
        //如果插入下标大于节点数，直接返回
        if (index > this.size) {
            return;
        }
        //如果下标小于等于0，在头节点新增
        if (index <= 0) {
            addAtHead(val);
            return;
        }
        //如果下标等于节点数，在尾节点新增
        if (index == this.size) {
            addAtTail(val);
            return;
        }
        //创建插入节点
        Node insertNode = new Node(val);
        //找到头节点
        Node temp = this.head;
        //找到插入位置的前一个节点
        for (int x = 0; x < index - 1; x++) {
            temp = temp.next;
        }
        //插入节点的下一个节点设置为前一个节点的下一个节点
        insertNode.next = temp.next;
        //前一个节点的下一个节点设置为当前插入节点
        temp.next = insertNode;
        //节点数+1
        size++;
    }

    public void deleteAtIndex(int index) {
        //如果删除下标大于节点数，直接返回
        if (index >= this.size) {
            return;
        }
        //如果下标等于0
        if (index == 0) {
            //数量>1,去掉头节点，将头节点的下个节点重新设置为头节点，数量-1
            if (size != 1) {
                Node temp = this.head.next;
                this.head = temp;
                size--;
                return;
            } else {
                //如果数量==1,头节点设为空，数量-1
                this.head = null;
                size--;
                return;
            }
        }
        Node temp = this.head;
        //找到删除位置的前一个节点
        for (int x = 0; x < index - 1; x++) {
            temp = temp.next;
        }
        //前一个节点的下个节点则是删除节点
        Node deleteTemp = temp.next;
        //删除节点的下一个节点则是前一个节点的下一个节点
        temp.next = deleteTemp.next;
        //数量-1
        size--;
    }

    public static void main(String[] args) {
        SinglyListNode linkedList = new SinglyListNode();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1, 2);   //链表变为1-> 2-> 3
        linkedList.get(1);            //返回2
        linkedList.deleteAtIndex(1);  //现在链表是1-> 3
        linkedList.get(1);            //返回3
    }
}
